我们有一个由 组成的排列,只能询问四次两个位置上的数的乘积。
下面是一些可能会考虑到的错误的策略(也是我做题时的思路),在这里放出体现我们的思考过程:
策略 1:每次询问两个相同的下标 和它本身。
这种策略是最容易想到的,但是这样的话只能询问出 个位置的值,剩下两个位置就没办法了。考虑其它策略。
策略 2:询问 与 的乘积,得到第一个数,此后三次询问 。
和策略 1 有着同样的问题。
正确策略
通过上面的思考,我们得到了一个结论:只有 个位置是显然不行的,考虑添加第五个位置。
我们可以询问 ,这样就能方便的获得和五个位置相关的信息。
具体解法
在按照上面的策略询问完前五个数后得到了四个答案(代码中记做 ),我们枚举所有 种可能的排列情况,对于每个排列,循环一遍判断是否符合询问得到的答案即可。
但是这样还不够,我们还要知道满足四个答案的排列是唯一的。
唯一性证明
自己口胡的,可能不太严谨,但是自认为比较好理解,可以手玩几个理解一下。
因为上面数列任意两个数的乘积都不同,我们想到,满足 的只有两种可能,即 与 交换。而上面就相当于固定了前五个数,因为数列中的六个数给定,可以通过排除来获得第六个数的信息。
唯一性得证,策略正确。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
int a[7] = {-1, 4, 8, 15, 16, 23, 42}, multiple[5];
int main() {
for(int i=1;i<=4;i++) {
printf("? %d %d\n", i, i+1);
fflush(stdout);
scanf("%d", &multiple[i]);
}
do {
bool _ = true;
for(int i=1;i<=4;i++) {
if(a[i] * a[i+1] != multiple[i]) {
_ = false;
break;
}
}
if(_) {
printf("! ");
for(int i=1;i<=6;i++) printf("%d ", a[i]);
puts("");
break;
}
}while(next_permutation(a+1, a+7));
return 0;
}